Grokking Database Fundamentals for Tech Interviews
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction to Database Systems
Course Overview
Overview of Databases
Core Components of Database
Database Architectures
Relational Vs. Non-relational Databases
Data Storage in DBMS
Data Storage Fundamentals
File Organization in DBMS
Data Compression and Encoding
Quiz
Indexing in DBMS
Introduction to Database Indexes
Single Level Indexing
Tree-Based Indexing Techniques
Hash-Based Indexing
Bloom Filters
Quiz
Understanding the Transaction
Atomicity
Consistency
Isolation
Durability
Quiz
Understanding the Concurrency Control
Optimistic vs. Pessimistic Concurrency Control
Lock-Based Concurrency Control
Timestamp-Based Concurrency Control
Multiversion Concurrency Control (MVCC)
Quiz
Fundamentals of Distributed Databases
Partitioning in Databases
Partitioning Types
Sharding in Databases
Distributed Query Processing
Quiz
Replication in Databases
Replication Topologies
Understanding the Consistency Models in Databases
The CAP Theorem and Its Implications
Quiz
Understanding the Consensus
Consensus algorithms
Leader Election Strategies
Quiz
Understanding the Fault Tolerance
Logging Mechanisms in Databases
Checkpointing and Recovery Basics
Coordinated Recovery in Distributed Systems
High Availability Through Replication and Failover
Ensuring Data Resilience: Redundancy, Mirroring, and Recovery
Quiz
Introduction to NoSQL
Key-Value Stores
Document-Oriented Databases
Column-Family and Wide-Column Stores
Graph Databases
Quiz
Quora System Design & Database Design
TikTok System Design & Database Design
Airbnb System Design & Database Design
Snapchat System Design & Database Design
Tree-Based Indexing Techniques

Tree-based indexing, a multi-level indexing technique is an efficient way to store and retrieve data in databases, especially when dealing with large datasets. Two widely used tree-based structures in database indexing are B-trees and B+ trees. These structures ensure logarithmic time complexity for search, insertion, and deletion operations. This section covers the workings of these structures, their differences, and their use in databases.

B-tree

A B-tree is a self-balancing search tree that keeps data sorted and allows searches, sequential access, insertions, and deletions to be performed in time. Unlike binary search trees, B-trees allow nodes to have multiple keys and more than two children, ensuring the tree remains balanced.

Key Features

  • Data is sorted within each node in ascending order.
  • Nodes contain multiple keys and pointers to child nodes.
  • The left child of a key contains smaller keys, and the right child contains larger keys.
  • All leaf nodes are at the same depth.

Structure of a B-tree

Below is an example of a B-tree with three levels:

B-Tree
B-Tree
  • Each node contains keys (e.g., 100, 155, 226) and pointers to child nodes.
  • The keys are arranged in ascending order, and child nodes split the data into ranges. For example:
    • Keys less than 100 go to the left child.
    • Keys between 100 and 155 go to the middle child.
    • Keys greater than 155 go to the right child.

Why Use B-tree Indexing?

Imagine storing a list of numbers in an unsorted array. Searching for a value would require scanning every element in the worst case, resulting in time complexity. Sorting the array and applying binary search improves the complexity to , but maintaining the sorted order during insertions or deletions becomes inefficient.

How B-trees Improve Efficiency

  • They maintain sorted data dynamically, avoiding the overhead of re-sorting.
  • Searching is efficient due to the balanced tree structure.
  • Each node contains multiple keys, reducing the height of the tree and the number of disk accesses.

Example Search in a B-tree

Suppose you are searching for 117 in the above B-tree:

  1. Start at the root node (100, 155, 226).
  2. Since 117 is greater than 100 but less than 155, move to the middle child node (128, 140).
  3. Within this node, move to the left child node (105, 117).
  4. Locate the key 117.

This search involves only three levels, demonstrating the efficiency of (O(\log(n))) operations.

B+ Tree

A B+ tree is an extension of the B-tree. It stores all the data at the leaf nodes and keeps internal nodes for navigation only. Additionally, leaf nodes are linked, enabling efficient sequential access.

Key Features

  • Internal nodes contain keys and pointers to child nodes.
  • All data is stored in the leaf nodes.
  • Leaf nodes are linked, facilitating fast range queries.
  • Like B-trees, all leaf nodes are at the same depth, maintaining balance.

Structure of a B+ Tree

Below is an example of a B+ tree:

Structure of B+ tree
Structure of B+ tree
  • Internal nodes (e.g., 13, 30, 9, 11, 16, 38) contain keys for navigation.
  • Leaf nodes (e.g., 1, 4, 9, 11, 12, 13, 16, 30, 38, 42) store all the data in sorted order.
  • Leaf nodes are connected via pointers, allowing efficient traversal for range queries.

Comparison of B-trees and B+ Trees

FeatureB-treeB+ tree
Data StorageKeys and data are stored in all nodesData is stored only in leaf nodes
Range QueriesLess efficientHighly efficient due to linked leaf nodes
TraversalRequires accessing multiple nodesSequential traversal via linked leaves

How Is Tree-Based Indexing Used in Databases?

Tree-based indexing, particularly B+ trees, is widely implemented in database systems to improve query performance.

1. Data Storage in B+ Trees

  • Databases store records in a table with multiple columns (e.g., Name, Marks, Age).
  • A unique index is created for each record (e.g., Index), which acts as a key in the B+ tree.

Example Table:

Image

2. Index Structure

  • Each key in the B+ tree references a record in the database.
  • Internal nodes facilitate navigation, while leaf nodes contain actual data or pointers to data pages.

Example B+ Tree for the Above Table:

Image
  • Keys (e.g., 12, 15, 24, 25) are used for indexing.
  • Leaf nodes store the actual data (e.g., Jone: Marks=5, Age=28).

Advantages of Indexing with B+ Trees

  • Efficient Searches: Lookups take time for the index and sequentially access data in the leaf nodes.
  • Reduced Disk Accesses: The hierarchical structure minimizes the number of pages read from disk.
  • Faster Range Queries: Linked leaf nodes allow quick traversal of sorted data.

How It Works:

  • The database first searches the index in the B+ tree to find the corresponding key.
  • Once the key is located, the leaf node points to the actual data record in the table.

Tree-based indexing, particularly B+ trees, is fundamental to modern database systems. While B-trees offer efficient general-purpose indexing, B+ trees excel in scenarios requiring range queries and sequential data access. By leveraging these structures, databases can handle large datasets efficiently, ensuring fast and scalable performance.

Single Level Indexing
Hash-Based Indexing
Mark as Completed

On this page

B-tree

Key Features

Structure of a B-tree

Why Use B-tree Indexing?

How B-trees Improve Efficiency

Example Search in a B-tree

B+ Tree

Key Features

Structure of a B+ Tree

Comparison of B-trees and B+ Trees

How Is Tree-Based Indexing Used in Databases?

  1. Data Storage in B+ Trees
  1. Index Structure

Advantages of Indexing with B+ Trees